package com.wtgroup.demo.mianshi.算法.二叉树;

import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;
import lombok.AllArgsConstructor;
import lombok.NoArgsConstructor;

/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/4 19:19
 */
public class Q_是否完全二叉树 {

    public static void main(String[] args) {
        Judger.of(() -> {
            Node tree = Util.generateRandomBST(RandomUtil.randomInt(0, 30), RandomUtil.randomInt());

            boolean r1 = new S1().doit(tree).isFull;
            boolean r2 = S2.isFull1(tree);

            return r1 == r2;
        }).start().print();
    }

    static class S1 {

        static Info doit(Node head) {
            if (head == null) {
                // true 是哨兵值
                return new Info(true, 0);
            }
            Info leftInfo = doit(head.left);
            Info rightInfo = doit(head.right);

            boolean isFull;
            int height;

            height = Math.max(leftInfo.height, rightInfo.height) + 1;

            if (leftInfo.isFull && rightInfo.isFull) {
                return new Info(leftInfo.height == rightInfo.height, height);
            }

            return new Info(false, height);
        }

        /*
        1. 不考虑自己,
            左右是完全, 得不出结果. 左子树完全, 右子树完全, 但两者高度不同.
            左右任意不是完全, 自己也不是完全
        2. 考虑自己.
            左右是完全, 且左右高度一致, 自己是完全
            左右任意不是完全, 自己也不是完全
         */
        @NoArgsConstructor
        @AllArgsConstructor
        static class Info {
            boolean isFull;
            int height;
        }
    }

    static class S2 {

        // 第一种方法
        // 收集整棵树的高度h，和节点数n
        // 只有满二叉树满足 : 2 ^ h - 1 == n
        public static boolean isFull1(Node head) {
            if (head == null) {
                return true;
            }
            Info1 all = process1(head);
            return (1 << all.height) - 1 == all.nodes;
        }

        public static class Info1 {
            public int height;
            public int nodes;

            public Info1(int h, int n) {
                height = h;
                nodes = n;
            }
        }

        public static Info1 process1(Node head) {
            if (head == null) {
                return new Info1(0, 0);
            }
            Info1 leftInfo = process1(head.left);
            Info1 rightInfo = process1(head.right);
            int height = Math.max(leftInfo.height, rightInfo.height) + 1;
            int nodes = leftInfo.nodes + rightInfo.nodes + 1;
            return new Info1(height, nodes);
        }
    }

}
